package algorithms;

import java.util.ArrayList;
import algorithms.Algorithm;
import animationEngine.AnimationState;

/**
 * The Class KMPTestAlgorithm, this class creates all of the animation states required
 * to animate the Knuth Morris Pratt Algorithm.
 * 
 * @author Andrei Palade
 * @author David McBrierty
 * @author Garry Sharp
 * @author Hristo Georgiev
 * @author John Dennis
 * @author Marco Sarconi
 * @version 1.0.1
 */
public class KMPTestAlgorithm implements Algorithm {

	/** The animation states. */
	ArrayList<AnimationState> animationStates = new ArrayList<AnimationState>();

	/* (non-Javadoc)
	 * @see algorithms.Algorithm#getStates(java.lang.String, java.lang.String)
	 */
	public ArrayList<AnimationState> getStates(String text, String pattern) {
		System.out.format("Text: %s\nPattern: %s\n", text, pattern);
		boolean found = false;

		int m = pattern.length(); // length of pattern
		int n = text.length(); // length of text

		int s = 0; // starting position in text t
		int i = 0; // curr position in text
		int j = 0; // curr position in pattern s

		/*
		 * Create starting animation state AnimationState(int textIndex, int
		 * patternPosition, int pseudoCodeLine, int textCharacterHighlight, int
		 * patternCharacterHighlight, boolean matches)
		 */

		int [] b = new int[m]; // create border table
		setUp(pattern, b); // set up the border table
		animationStates.add(new AnimationState(i, i, 0, i, j, false));
		for (int t = 0; t < m; t++)
			System.out.format("b[%d] = %d\n", t, b[t]);

		
		//animationStates.add(new AnimationState(i, i, 0, i, j, false));
		while (i < n) { // not reached end of text
			s = i - j;
			animationStates.add(new AnimationState(i, s, 1, i, j, false));
			System.out.format("i=%d, j=%d\n", i, j);
			//animationStates.add(new AnimationState(i, s, 2, i, j, false));
			if (text.charAt(i) == pattern.charAt(j)) { // if positions match
				animationStates.add(new AnimationState(i, s, 2, i, j, true));
				i++; // move on in text
				animationStates.add(new AnimationState(i, s, 3, i, j, true));
				j++; // move on in string
				animationStates.add(new AnimationState(i, s, 4, i, j, true));
				animationStates.add(new AnimationState(i, s, 6, i, j, true));
				if (j == m) {
					// reached end of string so a match
					animationStates.add(new AnimationState(i, s, 7, i, j, true));
					found = true;
					break;
				}
			}
			else { // mismatch; adjust current position in string using the border table
				animationStates.add(new AnimationState(i, s, 9, i, j, false)); 
				if (b[j] > 0) { // there is a common prefix/suffix
					animationStates.add(new AnimationState(i, s, 10, i, j, false));
					j = b[j]; // change position in string (position in text unchanged)
					animationStates.add(new AnimationState(i, s, 11, i, j, false));
				} else { // no common prefix/suffix
					animationStates.add(new AnimationState(i, s, 13, i, j, false));
					i = i -j+1; // move forward one position in text
					animationStates.add(new AnimationState(i, s, 14, i, j, false));
					j = 0; // start from beginning of the string
					animationStates.add(new AnimationState(i, s, 15, i, j, false));
				}
			}
		}
		if (!found) { // no occurrence
			animationStates.add(new AnimationState(i, s, 19, i, j, false));
			System.out.println("KMP: Pattern not found in text!");
		}
		return this.animationStates;
	}

	/**
	 * Sets the border table up.
	 *
	 * @param pattern the pattern
	 * @param b the b
	 */
	public static void setUp(String pattern, int[] b) {
		int m = pattern.length();
		b[0] = b[1] = 0;
		for (int i = 2; i < m; i++) {
			String substring = pattern.substring(0, i);
			b[i] = longestBorder(substring, i);
		}
	}

	/**
	 * Finds the longest border of a given string.
	 *
	 * @param str the string to find a border in
	 * @param length the length of the string
	 * @return the index in the string the broder occurs at
	 */
	private static int longestBorder(String str, int length) {
		int border = 0;
		for (int i = 1; i < length; i++) {
			/*
			 * Diagnostics:
			 * System.out.format("String: %s, Prefix: %s, Suffix: %s\n", str,
			 * str.substring(0, i), str.substring(length-i, length));
			 */
			if (str.substring(0, i)
					.compareTo(str.substring(length - i, length)) == 0)
				border = i;
		}

		/*
		 * Diagnostics: if (border > 0)
		 * System.out.format("Substring: %s, Border: %s\n", str,
		 * str.substring(0, border));
		 */
		return border;
	}	

}
